package zuo;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * 左程云基础课程
 */
public class Basic {
    public static void main(String[] args){
        int arr[] = {1,2,3,4,5,7};
        int num = 6;
        int max = getMax(arr);

        System.out.println(max);
    }

    /**
     * minWindow("ADOBECODEBANC", "ABC")
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s,String t){
        return null;
    }


    /**
     * 1.选择排序
     *
     * 依次从i~N-1选取最小值放到i位置上
     * @param arr
     */
    public static void selectionSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        for (int i = 0;i<arr.length-1;i++){
            int minIndex = i;// 最小值在i位置
            for (int j = i+1;j<arr.length;j++){//在i~N-1上的最小值的下标
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;//如果j位置的数小于最小值位置上的数，则把j位置变成最小值位置
            }
            swap(arr, i, minIndex);// 交换i和minIndex
        }
    }

    /**
     * 交换数组中i和j两个位置上的数的常规写法
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 用异或运算交换i和j位置上的数
     * 异或运算：值不同为1，相同为0
     * 要保证i和j所指向的内存空间不同
     * @param arr
     * @param i
     * @param j
     */
    public static void swapYiHuo(int[] arr, int i, int j){
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }


    /**
     * 2.冒泡排序：在0～i范围内做相邻两个数的交换
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        if (arr == null || arr.length <2){
            return;
        }
        for (int i = arr.length -1 ;i>0;i--){//在0～i范围内做相邻两个数的交换
            for (int j=0;j<i;j++){
                if (arr[j] >arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

    /**
     * 3.已知一个整型数组，有一种数出现了奇数次，其他所有数都是偶数次，求这个奇数次的数。
     * 要求时间复杂度为O（N），空间复杂度为O（1）
     * @param arr
     */
    public static void printOddTimesNum1(int[] arr){
        int res = 0;
        for (int cur : arr){
            res ^= cur;
        }
        System.out.println(res);
    }

    /**
     * 4.已知一个整型数组，有两种数出现了奇数次，其他所有数都是偶数次，求这两个奇数次的数。
     * 由于是两种数，所以这两个数肯定不相等，eor上必有一位是1，
     * 则数a与数b在这个位数上肯定有一个为0，一个为1，
     * 假设a上第rightOne位置上是0，找到arr中所有第rightOne位为0的数进行异或，则得出a,
     * 再与eor进行异或，得出b。
     * 要求时间复杂度为O（N），空间复杂度为O（1）
     * @param arr
     */
    public static void printOddTimesNum2(int[] arr){
        int eor = 0;
        for (int cur : arr){
            eor ^=cur;
        }
        //此时的eor是这两个奇数的异或
        int onlyOne = 0;
        int rightOne = eor & (~eor + 1);//取出eor最右边的1
        for (int cur :arr){
            if ((cur & rightOne) == 0){
                onlyOne ^=cur;
            }
        }
        int onlyAnotherOne = onlyOne ^ eor;
    }

    /**
     * 5.插入排序
     * @param arr
     */
    public static void insertionSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        // 0~i想有序
        for(int i=1;i<arr.length;i++){
            for (int j=i-1;arr[j]>arr[j+1]&&j>=0;j--){
                swapYiHuo(arr,j,j+1);
            }
        }
    }

    /**
     * 6.递归方式求一个数组中的最大值
     * @param arr
     * @return
     */
    public static int getMax(int[] arr){
        return process(arr,0,arr.length-1);
    }

    public static int process(int[] arr,int L,int R){
        if (L==R){
            return arr[L];
        }
        int mid = L+((R-L)>>1);//中点
        int leftMax = process(arr,L,mid);
        int rightMax = process(arr,mid+1,R);
        System.out.println(Math.max(leftMax, rightMax));
        return Math.max(leftMax, rightMax);
    }

    /**
     * 7.非降序列表中是否存在num的值
     * @param sortedArr
     * @param num
     * @return
     */
    public static boolean exist(int[] sortedArr,int num){
        if (sortedArr == null || sortedArr.length ==0){
            return false;
        }
        int L =0;
        int R = sortedArr.length -1;
        int mid =0;
        while (L<R){
            mid = L+((R-L)>>1);
            System.out.println("L=" + L +",R=" + R);
            System.out.println("mid=" + mid);
            if (sortedArr[mid] == num){
                return true;
            }else if (sortedArr[mid] >num){
                R=mid-1;
            }else {
                L=mid+1;
            }
        }
        return sortedArr[L]==num;
    }

    /**
     * 8.归并排序
     * 找出中点，分别排序，再用两个指针分别指向2个数组首位比较大小，小的往辅助空间里面放
     * @param arr
     */
    public static void mergeSort(int[] arr){
        if (arr == null || arr.length <2){
            return;
        }
        processMerge(arr,0,arr.length-1);
    }

    public static void processMerge(int[] arr,int L,int R){
        if (L==R){
            return;
        }
        int mid = L+((R- L)>>1);
        process(arr,L,mid);
        process(arr,mid+1,R);
        merge(arr,L,mid,R);
    }

    public static void merge(int[] arr,int L,int M,int R){
        int[] help = new int[R-L+1];
        int i=0;
        int p1=L;
        int p2=M+1;
        while (p1<=M && p2<=R){
            help[i++]=arr[p1] <= arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=M){
            help[i++]=arr[p1++];
        }
        while (p2<=R){
            help[i++]=arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[L+i]=help[i];
        }
    }

    /**
     * 9.求小和（第个数左边比当前数小的和累加起来）
     * @param arr
     * @return
     */
    public static int smallSum(int[] arr){
        if (arr == null || arr.length<2){
            return 0;
        }
        return processSmallSum(arr,0,arr.length-1);
    }

    public static int processSmallSum(int[] arr,int l,int r){
        if (l==r){
            return 0;
        }
        int mid =l+((r-l)>>1);
        return processSmallSum(arr,l,mid)+processSmallSum(arr,mid+1,r)+mergeSmallSum(arr,l,mid,r);
    }
    public static int mergeSmallSum(int[] arr,int l,int m,int r){
        int[] help =new int[r-l+1];
        int i=0;
        int p1=l;
        int p2=m+1;
        int res=0;
        while (p1<=m&&p2<=r){
            res+=arr[p1]<arr[p2]?(r-p2+1)*arr[p1]:0;
            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=m){
            help[i++]=arr[p1++];
        }
        while (p2<=r){
            help[i++]=arr[p2++];
        }
        for (i=0;i<help.length;i++){
            arr[l+i]=help[i];
        }
        return res;
    }

    /**
     * TODO
     * 10.逆序对问题
     * 11.荷兰国旗问题
     * 12.荷兰国旗问题扩展
     */

    /**
     * 13.快速排序
     * @param arr
     */
    public static void quickSort(int[] arr){
        if (arr==null||arr.length<2){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }


    public static void quickSort(int[] arr,int L,int R){
        if (L<R){
            swap(arr,L+(int)(Math.random()*(R-L+1)),R);
            int[] p=partition(arr,L,R);
            quickSort(arr,L,p[0]-1);
            quickSort(arr,p[1]+1,R);
        }
    }

    public static int[] partition(int[] arr,int L,int R){
        int less=L-1;
        int more=R;
        while (L<more){
            if (arr[L]<arr[R]){
                swap(arr,++less,L++);
            }else if (arr[L]>arr[R]){
                swap(arr,--more,L);
            }else{
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    /**
     * 大根堆的移动
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr,int index){
        while (arr[index] > arr[index-1]/2){
            swap(arr,index,(index-1)/2);
            index =(index-1)/2;
        }
    }

    /**
     * 返回大根堆的根结点且删除，再重新变成大根堆
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr,int index,int heapSize){
        int left =index*2+1;
        while(left <heapSize){
            int largest = left +1 <heapSize && arr[left+1]>arr[left]?left+1:left;
            largest=arr[largest]>arr[index]?largest:index;
            if (largest==index){
                break;
            }
            swap(arr,largest,index);
            index=largest;
            left=index*2+1;
        }
    }

    /**
     * 14.堆排序
     * 先变成一个大根堆，再把第一个数和最后一个数交换，循环
     * @param arr
     */
    public static void heapSort(int[] arr){
        if (arr==null|| arr.length<2){
            return;
        }
        for (int i=0;i<arr.length;i++){
            heapInsert(arr,i);
        }
        int heapSize=arr.length;
        swap(arr,0,--heapSize);
        while (heapSize>0){
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
    }

    /**
     * 15.已知一个几乎有序的数组，几乎有序是指如果把数组排好顺序的话每个元素移动的距离可以不超过k，且k相对于数组来说比较小。
     * 请选择一个合适的排序算法对这个数组进行排序（k给出）
     * @param arr
     * @param k
     */
    public static void sortedArrDistanceLessK(int[] arr,int k){
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index=0;
        for (;index<=Math.min(arr.length,k);index++){
            heap.add(arr[index]);
        }
        int i=0;
        for (;index<arr.length;i++,index++){
            heap.add(arr[index]);
            arr[i]=heap.poll();
        }
        while (!heap.isEmpty()){
            arr[i++]=heap.poll();
        }
    }

    /**TODO
     * 16.基数排序
     * @param arr
     */
    public static void radixSort(int[] arr){
        if (arr==null || arr.length <2){
            return;
        }

    }


    public static void radixSort(int[] arr,int L,int R,int digit){
        final int radix=10;
        int i=0,j=0;
        int[] bucket = new int[R-L+1];
        for (int d=1;d<=digit;d++){
            int[] count=new int[radix];
            for (i=L;i<=R;i++){

            }
        }
    }

    public static class Node{
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 判断一个链表是否为回文结构
     * 时间复杂度O（n）
     * @param head
     * @return
     */
    public static boolean isPalindrome1(Node head){
        Stack<Node> stack = new Stack<>();
        Node cur=head;
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (head !=null){
            if (head.value!=stack.pop().value){
                return false;
            }
            head=head.next;
        }
        return true;
    }

    public static boolean isPalindrome2(Node head){
        if (head==null ||head.next==null){
            return true;
        }
        Node right = head.next;
        Node cur = head;
        while(cur.next!=null&&cur.next.next!=null){
            right=right.next;
            cur=cur.next.next;
        }
        Stack<Node> stack = new Stack<>();
        while(right!=null){
            stack.push(right);
            right=right.next;
        }
        while(!stack.isEmpty()){
            if (head.value!=stack.pop().value){
                return false;
            }
            head=head.next;
        }
        return true;
    }

    public static boolean isPalidrome3(Node head){
        if (head == null || head.next==null){
            return true;
        }
        Node n1=head;
        Node n2=head;
        while(n2.next!=null&&n2.next.next!=null){
            n1=n1.next;
            n2=n2.next.next;
        }
        n2=n1.next;
        return true;
    }

}
